package leetcode;

public class Day20 {
    /*
    * 最长回文子串
    * */
    public String longestPalindrome(String s) {
        int n=s.length();
        int len=0;
        int mid=0;
        for (int i=0;i<n;i++){
            int tmp=str(s,i-1,i+1);
            if(i<n-1&&s.charAt(i)==s.charAt(i+1)){
                tmp=Math.max(tmp,str(s,i-1,i+2));
            }
            if(tmp>len){
                mid=i;
                len=tmp;
            }
        }
        int start=mid-len/2;
        if (len%2==0)start+=1;
        return s.substring(start,start+len);
    }

    private int str(String s, int l, int r) {
        while (l>=0&&r<s.length()){
            if (s.charAt(l)==s.charAt(r)&&l<r){
                l--;
                r++;
            }else {
                break;
            }
        }
        return r-l+1;
    }
    /*股票冷冻期*/
    public int maxProfit(int[] prices) {
        int n=prices.length;
        int[][] dp=new int[n][3];
        dp[0][0]=-prices[0];
        dp[0][1]=0;
        dp[0][2]=0;
        for (int i=1;i<n;i++){
            dp[i][0]=Math.max(dp[i-1][0],dp[i-1][2]-prices[i]);
            dp[i][1]=dp[i-1][0]+prices[i];
            dp[i][2]=Math.max(dp[i-1][1],dp[i-1][2]);
        }
        return Math.max(dp[n-1][1],dp[n-1][2]);
    }
}
